package 树.二叉搜索树;

import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

import static 抽象数据类型.TreeNode.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-28
 */
public class 判断是一颗二叉搜索树 {
    public static boolean isBST(TreeNode<Integer> node) {

         return isBST(node, null, null);
    }

    private static boolean isBST(TreeNode<Integer> root, TreeNode<Integer> maxNode, TreeNode<Integer> minNode) {
        if (root == null) {
            return true;
        }
        if (maxNode != null && root.val <= maxNode.val) {
            return false;
        }
        if (minNode != null && root.val >= minNode.val) {
            return false;
        }
        return isBST(root.left, maxNode, root) && isBST(root.right, root, minNode);
    }

    public  static TreeNode deleteNode(TreeNode<Integer> root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode<Integer> minNode = getMinNode(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        } else if (root.val > key) {
            root.left=deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    private static TreeNode<Integer> getMinNode(TreeNode<Integer> root) {
        if (root.left != null) {
            root = getMinNode(root.left);
        }
        return root;
    }

    public static void main(String[] args) {
        Integer[] str = new Integer[]{5, 3, 7, 1, 4,6 , 8};
        TreeNode treeNode =buildTree(new ArrayList<>(Arrays.asList(str)));
        deleteNode(treeNode, 3);
        System.out.println(isBST(treeNode));
    }
}
